package cn.sort;

//获取前驱 中序遍历
public class FindSoccessorNode {
    private static Node leftMost;

    public static Node getLeftMost(Node node) {
        //node.left == null 那么他的前驱就是null
        if (node == null) {
            return node;
        }

        Node right = node.right;
        while (right != null){
            node = node.right;
            right = node.right;
        }
        return node;
    }

    public static class Node{
        public int value;
        public Node left;
        public Node right;
        public Node parent;

        public Node(int data){
            this.value = data;
        }
    }

    //获取前驱节点
    public static Node getPreNode(Node node) {
        //
        if (null == node) {
            return node;
        }
        //如果有左子树,那么就是左子树的最后一个节点
        //如果没有左子树,那么就是node 是parent的右节点的 parent节点
        if (node.left != null) {
            return getLeftMost(node.left);
        } else {
            //没有左子树
            Node parent = node.parent;
            while (parent != null && parent.right != node){
                node = node.parent;
                parent = node.parent;
            }
            return parent;
        }
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        Node node1 = root;
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;

        node7.parent = node6.parent = node3;
        node4.parent = node5.parent = node2;
        node2.parent = node3.parent = node1;
       /*       1
           2        3
        4    5    6   7
       */
       //先序遍历  1 2 3 4 3 6 7
       //中序遍历  4 2 5 1 6 3 7
       //后序遍历 4 5 2 6 7 3  1



        //获取前驱节点
        Node preNode = getPreNode(node2);
        System.out.println(preNode);

    }
}
